package com.currentbp.Interesting.likou;

import org.junit.Test;

public class T1277countSquares {
    /*
示例 1：
输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
示例 2：
输入：matrix =
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
     */

    @Test
    public void t1() {
        System.out.println(countSquares(new int[][]{{1, 0, 1}, {1, 1, 0}, {1, 1, 0}}));
    }

    public int countSquares(int[][] matrix) {
        if (matrix == null || matrix.length <= 0) {
            return 0;
        }

        int result = 0;
        for (int i = 1; i <= matrix.length; i++) {
            result += doEachCOuntSquares(matrix, i);
        }

        return result;
    }

    private int doEachCOuntSquares(int[][] matrix, int len) {
        int result = 0;
        for (int i = 0; i < matrix.length - len + 1; i++) {
            for (int j = 0; j < matrix[0].length - len + 1; j++) {
                boolean isGood = isGoodSquare(matrix, i, j, i + len - 1, j + len - 1);
                if (isGood) {
                    result++;
                }
            }
        }
        return result;
    }

    private boolean isGoodSquare(int[][] matrix, int topI, int topJ, int downI, int downJ) {
        for (int i = topI; i <= downI; i++) {
            for (int j = topJ; j <= downJ; j++) {
                if (matrix[i][j] != 1) {
                    return false;
                }
            }
        }
        return true;
    }
}
